Sieć wifi

To zadanie pochodzi z Kółka Informatycznego w Staszicu.

Grupa młodsza

Pewnego słonecznego dnia dyrekcja szkoły postanowiła o konieczności rozprowadzenia sieci bezprzewodowej po całym liceum. Poinformowani o tym fakcie admini szkolnej sieci natychmiast rozpisali konkurs na projekt rozmieszczenia access pointów, tak aby w każdej klasie był zasięg.

Jesteś dzielnym mat-cosiem, chciałbyś więc taki konkurs wygrać - nagrodą główną jest bowiem zwiększenie quoty. Aby zrealizować swój cel, musisz tak zaplanować sieć, żeby w każdej klasie był najlepszy zasięg jaki jest tylko możliwy oraz żeby spełnione były pozostałe warunki. Aha... Do dyspozycji masz nie więcej niż K access pointów - jest kryzys, dyrekcja też musi oszczędzać.

Liceum, jak wszyscy wiemy, mieści się na dokładnie jednym piętrze. Wszystkie zaś klasy usytuowane są wzdłuż bardzo długiego, prostego korytarza. W szkolnym archiwum znalazłeś T planów, z odległościami każdej klasy od początku korytarza. Teraz zabierasz się do pracy...

Wejście

W pierwszej linii znajduje się liczba przypadków testowych. Pierwsza linia każdego przypadku zawiera dwie liczby całkowite n i m (1 <= m <= 100000), oznaczające kolejno liczbę access pointów, które może kupić dyrekcja, oraz liczbę klas w szkole. W kolejnych m liniach znajdują się odległości klas od początku korytarza (odległość taka nie przekracza miliona).

Wyjście

Dla każdego testu wypisz dokładnie jedną liczbę rzeczywistą - największą odległość pomiędzy klasa a access pointem znajdującym sie najbliżej tej klasy. Liczbę wypisz z dokładnością do jednej cyfrą po przecinku.

Przykład

1
2 3
1
3
10

1.0